package 链表;

/**
 *  https://leetcode-cn.com/problems/rotate-list/
 * @author 会玩的洋洋
 */
public class _61_旋转链表 {

    /**
     * 闭合为环
     * 可以将其看做一个循环链表
     * 先把链表的长度记录下来，通过计算需要移动的位数，如果移动位数是长度的倍数，则不需要移动
     * 移动几位，则第几位便为头部，再将第几位的上一个链表的next指向null。
     * @param head 目标节点
     * @param k 移动位数
     * @return ListNode
     */
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null || k == 0) {
            return head;
        }
        ListNode tail = head;
        int sum = 1;
        // 记录链表长度
        while (tail.next != null) {
            tail = tail.next;
            sum++;
        }
        int x = sum - k % sum;
        // 将链表变为循环链表
        tail.next = head;
        tail = head;
        ListNode newHead = null;
        // 查找到指定头部前一个节点位置
        for (int i = 0; i < x - 1; i++) {
            tail = tail.next;
        }
        newHead = tail.next;
        tail.next = null;
        return newHead;
    }

}
